package offer.singleLinkedList;

import java.util.Stack;

/**
 * Description：
 * Author: zhangc
 * Date：2017/7/27 14:17
 */
public class FirstCommonNode37 {

    /**
     * 两个栈的解法
     *
     * @param <T>
     * @return
     */
    public static <T> Node<T> getFirstCommonNode(Node<T> left, Node<T> right) {
        Stack<Node<T>> stackLeft = new Stack<>();
        Stack<Node<T>> stackRight = new Stack<>();
        while (left != null) {
            stackLeft.push(left);
            left = left.next;
        }
        while (right != null) {
            stackRight.push(right);
            right = right.next;
        }
        Node<T> temp;
        Node<T> rtnVal = null;
        while (!stackLeft.isEmpty() && !stackRight.isEmpty()) {
            temp = stackLeft.pop();
            if (temp.equals(stackRight.pop())) {
                rtnVal = temp;
            } else break;
        }
        return rtnVal;
    }

    public static <T> Node<T> getFirstCommonNodeNoStack(Node<T> left, Node<T> right) {
        Node l = left, r = right;
        int lsize = 0, rsize = 0;
        while (l != null) {
            ++lsize;
            l = l.next;
        }
        while (r != null) {
            ++rsize;
            r = r.next;
        }

        if (lsize >= rsize)
            for (int i = 0; i < lsize - rsize; i++)
                left = left.next;
        else
            for (int i = 0; i < rsize - lsize; i++)
                right = right.next;

        while (left != null && right != null) {
            if (left.equals(right))
                return left;
            else {
                left = left.next;
                right = right.next;
            }
        }
        return null;

    }


}
